package tree;

/**
 * 二叉排序树
 * 若左子树不空,则左子树所有节点的值均小于它的根节点的值
 * 若右子树不空,则右子树所有节点的值均大于它的根节点的值
 * @author mengxin
 *
 */
public class BinarySortTree {
	private Node root;
	
	public Node getRoot(){
		return this.root;
	}
	
	public class Node{
		private int element;
		
		private Node left;
		
		private Node right;
		
		public Node(int element){
			this(element,null,null);
		}
		
		public Node(int element,Node left,Node right){
			this.element = element;
			this.left = left;
			this.right = right;
		}	
	}
	
	public BinarySortTree(int element){
		this.root = new Node(element);
	}
	
	/**
	 * 创建二叉排序树
	 * @param data
	 */
	public void createTree(int[] data){
		if(data.length<=1){
			return;
		}
		for(int i=0;i<data.length;i++){
			insert(data[i],this.getRoot());
		}	
	}
	
	public boolean find(int value,Node node){
		if(getRoot().element>value){
			if(root.left!=null){
				return find(value,root.left);
			}else{
				return false;
			}
		}else if(getRoot().element<value){
			if(root.right!=null){
				return find(value,root.right);
			}else{
				return false;
			}
		}else{
			return true;
		}
	}
	
	/**
	 * 插入节点
	 * @param element
	 * @param root
	 * @return
	 */
	public boolean insert(int element,Node root){
		if(root != null){
			if(root.element>element){
				if(root.left!=null){
					return insert(element,root.left);
				}else{
					root.left = new Node(element);
					return true;
				}
			}else if(root.element<element){
				if(root.right!=null){
					return insert(element,root.right);
				}else{
					root.right = new Node(element);
					return true;
				}
			}else{
				return true;
			}
		}else{
			this.root = new Node(element);
			return true;
		}
		
	}
	
	/**
	 * 递归二叉排序树
	 * @param node
	 */
	public void recursive(Node node){
		if(node != null){
			if(node.left != null){
				recursive(node.left);
				System.out.println(node.element);
			}
			System.out.println(node.element);
			if(node.right != null){
				recursive(node.right);
				System.out.println(node.element);
			}	
		}
		
	}
	
	
	/**
	 * 删除节点
	 */
	public Node remove(int element,Node node){
		if(getRoot().element == element){
			if(getRoot().left == null&&getRoot().right==null){
				root=null;
			}else if(getRoot().left==null&&getRoot().right!=null){
				root = root.right;
			}else if(getRoot().left!=null&&getRoot().right!=null){
				root = root.left;
			}else{
				//被删除的节点含有两个子节点
				//根据删除节点的类型，分成以下几种情况
	            //①如果被删除的节点是叶子节点，直接删除
	            //②如果被删除的节点含有一个子节点，让指向该节点的指针指向他的儿子节点
	            //③如果被删除的节点含有两个子节点，找到左子树的最大节点，并替换该节点
                Node newRoot = root.left;
                while (newRoot.left != null){
                    newRoot = newRoot.left;//找到左子树的最大节点
                }
                root.element = newRoot.element;
                root.left = remove(element,root.left);
			}
		}else if(getRoot().element > element){
			remove(element,root.left);
		}else if(getRoot().element < element){
			remove(element,root.right);
		}
		return root;
	}
	
	public static void main(String[] args) throws Exception{
		int[] data = new int[]{34,29,16,86,74,36,29,10,6,13,88,27};
		BinarySortTree tree = new BinarySortTree(34);
		tree.insert(29, tree.getRoot());
		tree.insert(16, tree.getRoot());
		tree.insert(86, tree.getRoot());
		tree.insert(74, tree.getRoot());
		tree.recursive(tree.getRoot());
//		tree.createTree(data);
//		tree.find(29);
	}
}
